The subject invention relates to a method and system for generating secret inputs, such as keys, to a cryptographic system. More particularly it relates to a method and system for generating inputs, typically in the form of binary strings, which are “hard” to guess. By “hard” herein is meant that given realistic computational resources a secret input cannot be discovered, given less than all the inputs used to create the secret input, in less than exponential time. Still more particularly it relates to a method and system for generating keys for digital postage meters which rely on cryptographic techniques to create secure, digitally printed postal indicia.
Encryption, Digital Signature algorithms, and Key Agreement Protocols and similar cryptographic systems rely on two basic assumptions to keep information secure: (i) the algorithms used are sound, and cannot be attacked directly. That means you cannot derive information about inputs to the algorithm that you did not know before hand; nor can you derive the output of the algorithm unless you know all the inputs; and (ii) any secret input of the algorithm is hard to guess. Typically secret inputs are inputs such as: a secret key, a random value used for “blocking” (i.e. used to hide other information), or the private portion of a public key pair. (As used herein the terms “key” or “cryptographic key” are meant to include any string of random bits for cryptographic applications, such as a secret input or a hard to guess value from which a secret input is derived; e.g. a hard to guess value from which a public/private key pair is derived; as well as strings used in applications where the random bits become known and still strong security is required.)
Deterministic Random Bit Generators (DRBG's) are used to satisfy this second assumption, and are used throughout standard cryptographic protocols and operations such as: SSL/TLS Secure Sockets Layer Protocol, DSA—Digital Signature Algorithm, Diffie-Hellman Key Exchanges, RSA Encryption and Signing Algorithms, etc. DRBG's provide the basic hard to guess inputs to such cryptographic operations. Typically DRBG's include an initialization routine to generate an initial state variable, a generation routine to generate a requested secret input, and can include a reseed routine to recover security properties in the event the DRBG is compromised.
The current family of ANSI (American National Standards Institute) approved DRBG's (based on Data Encryption Standard (DES) and Secure Hash Algorithm (SHA) standards) are aging in the sense of being antiquated by newer algorithms and stronger security requirements. In fact DES is broken in the sense that a sub-exponential algorithm to break it is known.
Current security specifications for Advanced Encryption Standard (AES) and Elliptic Curve Cryptography (ECC) provide security that require on the order of 2256 computational operations to break an algorithm. While DRBG's that adequately provide that level of security have been described; that is which can require a number of operations of the same order to break the algorithm and to discover the secret key used, thus maintaining overall security; such DRBG's are believed to be relatively complex, and difficult to design and analyze.
It is also advantageous to provide a DRBG having a consistent, or “flat”, forward secrecy profile and backward secrecy, against all known state assumptions. Backward secrecy is the property that even with knowledge of the current state of the DRBG it remains hard to determine previous components of the state. A flat forward secrecy profile is the property that even with any (less than complete) knowledge of the current state it remains hard to predict future output of the DRBG, or future unknown components of the state.
Thus it is an object of the subject invention to provide a method and system for generating secret inputs that provide increased levels of security for cryptographic systems, and that has the properties of a flat forward secrecy profile and backwards secrecy, while having a relative degree of simplicity of design and ease of analysis.